//
// Created by Administrator on 2021/8/2.
//
//给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>

using namespace std;

class Solution {
public:
    int firstUniqChar(const string &s) {
        int n = (int) s.size();
        // -1：未出现 -2：重复
        vector<int> pos(26, -1);
        for (int i = 0; i < n; ++i) {
            int p = s[i] - 'a';
            // 没出现过
            if (pos[p] == -1)
                pos[p] = i;
                // 出现过 重复
            else if (pos[p] >= 0)
                pos[p] = -2;
        }
        int ans = n;
        for (int i = 0; i < 26; ++i) {
            if (pos[i] >= 0)
                ans = min(ans, pos[i]);
        }
        return ans == n ? -1 : ans;
    }
};

class Solution2 { // hash两次遍历
public:
    int firstUniqChar(string s) {
        unordered_map<int, int> frequency;
        for (char ch: s) {
            ++frequency[ch];
        }
        for (int i = 0; i < s.size(); ++i) {
            if (frequency[s[i]] == 1) {
                return i;
            }
        }
        return -1;
    }
};

class Solution3 { // 借助队列
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> position;
        queue<pair<char, int>> q;
        int n = (int)s.size();
        for (int i = 0; i < n; ++i) {
            if (!position.count(s[i])) {
                position[s[i]] = i;
                q.emplace(s[i], i);
            } else {
                position[s[i]] = -1;
                while (!q.empty() && position[q.front().first] == -1) {
                    q.pop();
                }
            }
        }
        return q.empty() ? -1 : q.front().second;
    }
};

int main() {
    Solution solution;
    cout << solution.firstUniqChar("leetcode") << endl;
    cout << solution.firstUniqChar("loveleetcode") << endl;
    return 0;
}
